1. Technical Field
The present invention relates to intermediate language expressions in a compiler of a data processing system. In particular, the present invention relates to defining and embedding intermediate language pattern in a compiler of a data processing system. Still more particular, the present invention relates to a programming framework for pattern matching and transformation of intermediate language expression trees in a compiler of a data processing system.
2. Description of Related Art
Typically, when a programmer developed a program, the programmer compiles the program using a compiler, which parses the source program and generates an intermediate representation for the program. An example of a compiler is an IBM XL compiler and an example of a generated intermediate representation is W-code, both of which are available by International Business Machines Corporation.
The intermediate representation provides a stack-based representation of expressions in the program. For example, if the program includes an expression ‘x+y’, the intermediate representation of the expression becomes ‘(add (x)(y))’ or as follows:

In this example, operator ‘+’ is applied to the stack after arguments y and x.
In another example, if the program includes an express ‘x+(y+z)’, the intermediate representation of the expression becomes ‘add((x) (add (y) (z)))’ or as follows:

In this example, argument ‘y’ and ‘z’ are applied to the stack before operator ‘+’. The result is then applied to the stack along with argument ‘x’ before root operator ‘+’ is applied.
Pattern matching of intermediate representation is a common technique used to locate predictable statements and expressions and retrieve specific elements, in order to create derived expressions. An example of a predictable statement or expression may be an expression that has an induction variable, such as ‘x++’. Expression ‘x++’ may be represented in an intermediate representation as ‘(str x (add (lod x) (ldc 1)))’ or as follows:

Pattern matching of intermediate representation helps to identify a loop that has such induction variable, which adds a constant value to x for every iteration of the loop. Therefore, pattern matching of intermediate representation is a useful technique in loop optimization.
However, most existing pattern matching code is hand crafted for specific patterns. Thus, a specific pattern matching code is hand-crafted for expression ‘x++’. In most cases, pattern matching code only handles certain common expressions and not other less common expressions. While a generalized pattern matching code or pattern matcher for a given pattern may be written, it is cumbersome for the programmer, since backtracking is needed in many cases to handle possible different forms of a matching expression.
In addition, existing pattern matcher code does not provide the capability of easily constructing complex pattern matchers and pattern transformers as objects using grammatical building blocks.
Therefore, the ability to construct and pass these constructed objects as parameters to functions to perform pattern matching and transformation, as well as embedding these constructed objects within a program is desirable. Furthermore, the extensibility of the pattern matcher is desired, such that performance of the compiler may be improved with embedded pattern matchers.
Therefore, it would be advantageous to have an improved method, apparatus, and computer instructions for easy pattern matching of intermediate representation and transformation of intermediate language expression trees, such that pattern matching may be generalized to cover less common expression without much development effort, and can be embedded within a source program.